1. Technical Field
The invention is related to processes and apparatus for compressing and decompressing images.
2. Background Art
A fundamental goal of image compression is to reduce the amount of data necessary to represent an image while maintaining acceptable image fidelity. Examples of important applications include image transmission and image storage.
Image compression has long been an active research field, and various image compression methods have been developed. However, many of these methods are not practically useful, either because they cannot achieve high compression ratio with good image fidelity (as in the case of differential pulse code modulation or DPCM), or because they do not have tractable computational complexity (as in the case of "second generation" multiscale edge coding. In the prior art, the best image compression methods that have been used practically in an imaging system are transform coding, vector quantization (VQ), and a combination of thereof. These transform-quantization methods offer compression ratios of about 10:1 on a single frame gray-level image. When higher compression ratios are considered, a transform-quantization method may introduce unacceptable artifacts such as ringing, blurring, and blocking.
A general framework of a transform-quantization compression system consists of (1) a transform operator, (2) a quantizer, and (3) an entropy coder.
In the compression phase:
the transform operator transforms the source image to transform coefficients that can be coded more efficiently; PA1 the quantizer maps the transform coefficients into a smaller set of symbols in order to reduce the space of the symbols to be encoded; and PA1 the entropy coder converts the symbols into a more compact bit stream as the compressed data. PA1 the entropy coder converts the bit stream back to the symbols; PA1 the quantizer maps the symbols back to the transform coefficients; PA1 the transform operator inverts the transform coefficients back to an image.
In the decompression phase:
The purpose of the transform is to convert correlated image pixel values into relatively uncorrelated transform coefficients. Depending on how the transforms are computed and how the data are organized, the transforms are traditionally divided into two categories: subband transforms and block transforms, and the coding methods based on these transforms are called subband coding and block transform coding, respectively. A subband transform is computed by a multirate filter bank system. The output data are organized as a set of subimages. Each subimage corresponds to a frequency subband. A block transform is a transform applied to non-overlapping blocks of the image. Each block of pixels is transformed to a block of coefficients. Since it is trivial to convert the data in block organization to subimage organization, a block transform is mathematically equivalent to a subband transform. Therefore, a subband transform unifies all the transforms used for transform coding. The transforms that have been used for transform coding include discrete cosine transform (DCT), Wals-Hadamard transform (WHT), Haar transform, Karhunen-Loeve transform (KLT), discrete wavelet transform (DWT), and wave-packets transform.
A quantizer for the transform coefficients consists of a partition of the transform coefficient space into disjointed bins, each bin having a reproduction value. In the compression phase, the quantizer maps each transform coefficient to the index of the bin it belongs to. These indices, forming a reduced representation of the transform coefficients, are the symbols to be encoded. The quantization reduces the space of the symbols to be encoded but also reduces the accuracy of the image information. In the decompression phase, the quantizer maps each bin index to its reproduction value. The difference between a transform coefficient value and its quantization reproduction value is the quantization distortion.
It is believed that the quantization on grouped values produces better results than the quantization on individual values. The transform coefficients can be grouped into vectors by associated parameters such as position or frequency. A k-dimensional vector quantizer consists of a partition of k-dimensional vector space into disjointed bins, each bin having a k-dimensional reproduction vector. In the compression phase, the quantizer maps each vector of k transform coefficients into the index of the bin the vector belongs to; in the decompression phase, the quantizer maps each bin index to its reproduction vector. A motivation for transform-quantization coding is that the image information is typically concentrated on low frequencies, and the high frequency information is less important and thus can be reduced more severely. Accordingly, the low frequency coefficients are quantized with minimal bin size while the high frequency coefficients are quantized with larger bin sizes. In practice, most high frequency coefficients are mapped to the zero bin and discarded before the encoding. Most quantization distortions on high frequency coefficients do not damage the image fidelity.
A problem with transform-quantization coding is that the truncation of high frequency coefficients introduces artifacts. While most high frequency coefficients are insignificant, those associated with edges and lines are very important. Truncating those high frequency coefficients will blur the edges and lines as well as cause ringing effects (Gibbs phenomenon).
In addition, a more severe problem with block transform coding is artifacts known as blocking artifacts. Blocking artifacts are the discontinuities between adjacent blocks introduced by the block transform coding, particularly at a high compression ratio.
A method for deblocking, or reducing the blocking artifacts, is to impose a number of constraints on the reconstruction image. One such constraint is the bandlimited constraint, which is derived from the fact that the vertical and horizontal high frequency components contained in the reconstruction image are due to the blocking artifacts and are missing in the original image. By imposing the bandlimited constraint the reconstruction image is free from the blocking artifacts. Another constraint is the quantization constraint, which is derived from the quantization of the transform coefficients. The data of the quantization specify the upper and lower bounds on the transform coefficients. Imposing the quantization constraint ensures that the reconstruction image is consistent with the compression data. These two constraints define two convex sets of images. The deblocking procedure takes the reconstruction image of a block transform coding system as an initial image and alternates projecting the image onto the two convex sets until the image reaches the intersection of the two sets. The resulted image satisfies both the bandlimited constraint and the quantization constraint. Therefore, it is free from the blocking artifacts and is consistent with the compression data.
However, the bandlimited constraint is rather ad hoc. As the price for deblocking, it causes artifacts of blurring and introduces distortions of image features and removes horizontal and vertical edges that actually present in the original image.